Міністерство освіти та науки України
НУ „Львівська політехніка”
Лекція №13
з курсу: «Застосування засобів об’єктно-орієнтованого програмування в лінгвістичних задачах»
Львів - 2010
11. Алгоритми пошуку в тексті.
11.1. Простий алгоритм Пошуку в тексті
(Задача точного пошуку)
Першим з таких завдань буде завдання про пошук з точним збігом. Це
завдання вирішується, наприклад, в текстовому редакторові, коли
користувач розшукує в редагованому тексті зразок, але практичне її
використання даним прикладом не обмежується. Тому в науковій літературі
завданню про пошук приділяється дуже велика увага.
Найпростішим алгоритмом пошуку підстрічки в стрічці можна вважати
наступний (псевдокод на Pascal):
{пошук всіх входжень підстрічки P в стрічку T}
<Ввести значення стрічки T і підстрічки P>
n := length(t);
m := length(p);
for s := 0 to n - m do
begin
j := 1;
while ( j<=m ) and ( p[j] = t[j+s] ) do
inc(j);
if j > m then
writeln(s); {рядок Р входить в T із зсувом s}
end;
Цей алгоритм хоч і правильний, але дуже неефективний. Складність
цього алгоритму у найгіршому випадку – O(m(n-m+1)). Ми розглянемо
клас алгоритмів швидкого пошуку підстрічок, що мають істотно менший
порядок складності. Всі реалізації алгоритмів приводитимемо на мові
Pascal.
Почнемо з визначень. Задача пошуку підстрічок полягає в
наступному: існує деякий текст T[1..n] і текст який треба знайти P[1..m]
(m.n). Потрібно знайти всі входження тексту P в текст Т. Текст який треба
знайти далі будемо називати «зразком». Будемо казати, що зразок P
входить в T з зсувом s (або те ж саме, що s – допустимий зсув), якщо
P[1..m] = T[s+1...s+m] (0 . s . n-m). У задачі потрібно знайти всі
допустимі зсуви s. Робота простого алгоритму, код якого показано вище,
показана на мал. 1.
Малюнок 1.
Зразок P «рухається» вправо зовнішнім циклом по s. Далі, циклом по
j порівнюється кожна буква зразка P з відповідною буквою тексту T. Якщо
j>m, означає повний збіг , і поточне значення s – і є допустимим зсувом.
11.1. Алгоритм Кнута, Моріса і Пратта (КМП).
Цей алгоритм одержав свою назву від імен його авторів. Він
складається з двох етапів: підготовчого (побудови префікс-функції) і
основного (власне пошуку).
Підготовчий етап. Для довільного слова X розглянемо всі його
префікси, що одночасно є його суфіксами, і серед них виберемо
щонайдовший (не рахуючи самого X). Його позначатимемо L(X), і далі в
тексті його називатимемо найбільшим префікс-суфіксом. Наприклад,
L(abcab)= ab, L(cabcabc) = cabc. Через f(X) позначимо довжину
найбільшого префікс-суфікса Х (тобто довжину L(X)). Функцію f(X)
називатимемо префікс-функцією. Наприклад, f(abcab)= 2, тому що
L(abcab) = ab; f(cabcabc) = 4, тому що L(cabcabc) = cabc.
На підготовчому етапі КМП-алгоритму нам треба обчислити значення
f() для всіх префіксів P[1..k] (k=1..M). Відповідь на питання «для чого?»
дамо пізніше. Спершу про те, як це зробити. Дані визначимо так:
const
MAXPLEN = 24;
var
m: integer; { довжина зразка }
p: string; { зразок }
f: array[1..MAXPLEN] of integer; { префікс-функція}
Тут f[k] означатиме f(P[1..K]). Якщо розглянути послідовність слів
X, L(X), L(L(X)), L(L(L(X))), ... то бачимо, що кожен наступний її елемент
буде префікс-суфіксом попереднього, і ця послідовність закінчується
порожнім рядком. Послідовність чисел length(X), f(X), f(f(X)), f(f(f(X))).
(відповідна вищезгаданою) убуває і закінчується нулем. Алгоритм
обчислення f[k] буде наступним. Припустимо, ми вже обчислили f[1], ...,
f[k-1]. На k-м кроці нам треба обчислити f[k].
Малюнок 2.
Розглянемо P[k]. Символи, які ми порівнюватимемо, позначені темно-
сірим кольором (мал. 2). Якщо P[k]= P[f[k-1]+1], то f[k]= f[k-1]+1
(оскільки P[1..f[k-1]] – суфікс P[1..k-1], і отже P[1..f[k-1]+1] – суфікс
P[1..k]). Якщо ж P[k]<> P[f(k-1)+1], то порівнянний P[k] з P[f[f[k-
1]]+1]. Якщо останні рівні, то f[k]= f[f[k-1]]+1. І так далі. Таким чином
ми дійдемо f[k]= f (q)[k-1]+1 (індекс q означає номер ітера...
